home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / CH_6.1 / XVOR / HEAP.C < prev    next >
C/C++ Source or Header  |  1999-09-11  |  2KB  |  123 lines
  1. /* 
  2.  * heap.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * HEAP.C
  11.  *
  12.  */
  13. #include <stdlib.h>
  14. #include "vor.h"
  15.  
  16.  
  17. void
  18. PQinsert (he, v, offset)
  19.      struct Halfedge *he;
  20.      struct Site *v;
  21.      float offset;
  22. {
  23.   struct Halfedge *last, *next;
  24.  
  25.   he->vertex = v;
  26.   ref (v);
  27.   he->ystar = (float) (v->coord.y + offset);
  28.   last = &PQhash[PQbucket (he)];
  29.   while ((next = last->PQnext) != (struct Halfedge *) NULL &&
  30.          (he->ystar > next->ystar ||
  31.         (he->ystar == next->ystar && v->coord.x > next->vertex->coord.x))) {
  32.     last = next;
  33.   }
  34.  
  35.   he->PQnext = last->PQnext;
  36.   last->PQnext = he;
  37.   PQcount += 1;
  38. }
  39.  
  40. void
  41. PQdelete (he)
  42.      struct Halfedge *he;
  43. {
  44.   struct Halfedge *last;
  45.  
  46.   if (he->vertex != (struct Site *) NULL) {
  47.     last = &PQhash[PQbucket (he)];
  48.     while (last->PQnext != he)
  49.       last = last->PQnext;
  50.     last->PQnext = he->PQnext;
  51.     PQcount -= 1;
  52.     deref (he->vertex);
  53.     he->vertex = (struct Site *) NULL;
  54.   }
  55. }
  56.  
  57. int
  58. PQbucket (he)
  59.      struct Halfedge *he;
  60. {
  61.   int bucket;
  62.  
  63.   bucket = (int) ((he->ystar - ymin) / deltay * PQhashsize);
  64.   if (bucket < 0)
  65.     bucket = 0;
  66.   if (bucket >= PQhashsize)
  67.     bucket = PQhashsize - 1;
  68.   if (bucket < PQmin)
  69.     PQmin = bucket;
  70.  
  71.   return (bucket);
  72. }
  73.  
  74.  
  75.  
  76. int
  77. PQempty ()
  78. {
  79.   return (PQcount == 0);
  80. }
  81.  
  82.  
  83. struct Point
  84. PQ_min ()
  85. {
  86.   struct Point answer;
  87.  
  88.   while (PQhash[PQmin].PQnext == (struct Halfedge *) NULL) {
  89.     PQmin += 1;
  90.   }
  91.   answer.x = PQhash[PQmin].PQnext->vertex->coord.x;
  92.   answer.y = PQhash[PQmin].PQnext->ystar;
  93.  
  94.   return (answer);
  95. }
  96.  
  97. struct Halfedge *
  98. PQextractmin ()
  99. {
  100.   struct Halfedge *curr;
  101.  
  102.   curr = PQhash[PQmin].PQnext;
  103.   PQhash[PQmin].PQnext = curr->PQnext;
  104.   PQcount -= 1;
  105.  
  106.   return (curr);
  107. }
  108.  
  109.  
  110. void
  111. PQinitialize ()
  112. {
  113.   int i;
  114.  
  115.   PQcount = 0;
  116.   PQmin = 0;
  117.   PQhashsize = 4 * sqrt_nsites;
  118.   PQhash = (struct Halfedge *) myalloc (PQhashsize * sizeof *PQhash);
  119.  
  120.   for (i = 0; i < PQhashsize; i += 1)
  121.     PQhash[i].PQnext = (struct Halfedge *) NULL;
  122. }
  123.